from typing import List
import heapq

class Solution:
    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:
        # 计算两点之间的代价
        def cost(p1, p2):
            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

        # 构建图，包含特殊路径和普通路径
        graph = {}
        for road in specialRoads:
            x1, y1, x2, y2, road_cost = road
            if (x1, y1) not in graph:
                graph[(x1, y1)] = []
            if (x2, y2) not in graph:
                graph[(x2, y2)] = []
            graph[(x1, y1)].append(((x2, y2), road_cost))
            graph[(x2, y2)].append(((x1, y1), road_cost))


        # 将起点和终点与其他点连接
        for point in graph:
            graph[point].append((start, cost(start, point)))
            graph[point].append((target, cost(target, point)))

        start = tuple(start)
        target = tuple(target)
        graph[start] = [(point, cost(start, point)) for point in graph]
        graph[target] = []

        # 使用Dijkstra算法找到最短路径
        visited = set()
        min_heap = [(0, start)]

        while min_heap:
            cur_cost, cur_point = heapq.heappop(min_heap)
            if cur_point == target:
                return cur_cost
            if cur_point in visited:
                continue
            visited.add(cur_point)

            for neighbor, edge_cost in graph[cur_point]:
                if neighbor not in visited:
                    heapq.heappush(min_heap, (cur_cost + edge_cost, neighbor))

        return -1


if __name__ == '__main__':

    start = [1, 1]
    target = [4, 5]
    specialRoads = [[1, 2, 3, 3, 2], [3, 4, 4, 5, 1]]
    print(Solution().minimumCost(start, target, specialRoads))  # 输出：5

    start = [3, 2]
    target = [5, 7]
    specialRoads = [[3, 2, 3, 4, 4], [3, 3, 5, 5, 5], [3, 4, 5, 6, 6]]
    print(Solution().minimumCost(start, target, specialRoads))  # 输出：7
